class Solution:
    def maxA(self, n: int) -> int:
        # dp[i] = [当前总长度,剪贴板总长度]
        dp = [[] for _ in range(n + 1)]
        dp[0].append((0, 0))

        for i in range(n):
            for j, d in dp[i]:
                # 按A或(Ctrl+V)
                if i + 1 <= n:
                    dp[i + 1].append((j + max(d, 1), d))

                # 按(Ctrl+A)和(Ctrl+C)
                if i + 2 <= n:
                    dp[i + 2].append((j, j))

        return max(j for j, d in dp[n])


if __name__ == "__main__":
    print(Solution().maxA(3))  # 3
    print(Solution().maxA(7))  # 9
